The present invention relates generally to integrated circuit memory devices and, more particularly, to an apparatus and method for implementing matrix-based search capability in content addressable memory (CAM) devices.
A content addressable memory (CAM) is a storage device in which storage locations can be identified by both their location or address through a read operation, as well as by data contents through a search operation. An access by content starts by presenting a search argument to the CAM, wherein a location that matches the argument asserts a corresponding match line. One use for such a memory is in dynamically translating logical addresses to physical addresses in a virtual memory system. In this case, the logical address is the search argument and the physical address is produced as a result of the dynamic match line selecting the physical address from a storage location in a random access memory (RAM). Accordingly, exemplary CAM search operations are used in applications such as address-lookup in network ICs, translation lookaside buffers (TLB) in processor caches, pattern recognition, data compression, etc. CAMs are also frequently used for address-look-up and translation in Internet routers and switches.
A CAM typically includes an array of CAM cells arranged in rows and columns, where each row of the CAM array corresponds to a stored word. The CAM cells in a given row couple to a word line and a match line associated with the row. The word line connects to a control circuit that can either select the row for a read/write operation or bias the word line for a search. The match line carries a signal that, during a search, indicates whether the word stored in the row matches an applied input search word. Each column of the conventional CAM array corresponds to the same bit position in all of the CAM words, while the CAM cells in a particular column are coupled to a pair of bit lines and a pair of search-lines associated with the column. A search data is applied to each pair of search lines, which have a pair of complementary binary signals or unique ternary signals thereon that represent a bit of an input value. Each CAM cell changes the voltage on the associated match line if the CAM cell stores a bit that does not match the bit represented on the attached search lines. If the voltage on a match line remains unchanged during a search, the word stored in that row of CAM cells matches the input word.
As will thus be appreciated, conventional CAM devices are only capable of searching words of data that are stored in one dimension (1D), comparing, for example, the search data against all words that run along the word line (WL) direction. In this instance, such searching capability does not also extend to the data bits along a common bit line (BL) in conventional CAM. Regardless of the particular direction (row versus column) of a 1D CAM search, a conventional CAM device is not capable of simultaneously comparing an entire matrix of search data with an entire matrix of stored data. Accordingly, it would be desirable to be able to implement CAM structures that provide the capability of full data matrix searching.